Analysis of Algorithms Week 3

这次回顾第三周的内容。

课程主页：https://www.coursera.org/learn/analysis-of-algorithms

Exercise

3.20

Solve the recurrence $a_{n}=3 a_{n-1}-3 a_{n-2}+a_{n-3} \text { for } n>2$ with $a_0=a_1=0$ and $a_2=1$.

首先对原式进行改写：

$$a_{n}=3 a_{n-1}-3 a_{n-2}+a_{n-3} +\delta_{n2}$$

那么

$$\begin{aligned} a_nz^n &= 3 a_{n-1}z^n -3 a_{n-2}z^n +a_{n-3} z^n +\delta_{n2}z^n \\ A(z)&= 3zA(z)-3z^2 A(z) +z^3A(z) +z^2\\ A(z) &=\frac{z^2}{ 1-3z+3z^2 -z^3} =\frac{z^2}{(1-z)^3}\\ a_n &=\binom n2 =\frac{n(n-1)}{2} \end{aligned}$$

3.28

Find an expression for $\left[z^{n}\right] \frac{1}{\sqrt{1-z}} \ln \frac{1}{1-z}$.

Hint. Expand $(1-z)^{-\alpha}$ and differentiate with respect to $\alpha$.

$$\begin{aligned} (1-z)^{-\alpha} &= \sum_{n=0}^{\infty} \binom {-\alpha} n (-z)^n \\ &= \sum_{n=0}^{\infty} \frac{(-\alpha)(-\alpha -1)\ldots (-\alpha -n+1)}{n!} (-z)^n\\ &=\sum_{n=0}^{\infty}\frac{(\alpha)(\alpha+1)\ldots (\alpha+n-1)}{n!} z^n \end{aligned}$$

两边关于$\alpha $求导可得

$$\begin{aligned} (1-z)^{-\alpha}\ln \frac 1{1-z} &=\sum_{n=0}^{\infty} \left(\sum_{i=0}^{n-1} \frac 1 {\alpha +i}\right)\frac{(\alpha)(\alpha+1)\ldots (\alpha+n-1)}{n!} z^n \end{aligned}$$

取$\alpha =\frac 1 2$可得

$$\begin{aligned} \left[z^{n}\right] \frac{1}{\sqrt{1-z}} \ln \frac{1}{1-z} &=\left(\sum_{i=0}^{n-1} \frac 1 {\alpha +i}\right)\frac{(\alpha)(\alpha+1)\ldots (\alpha+n-1)}{n!} \Big| _{\alpha= \frac 12 }\\ &=\left(\sum_{i=0}^{n-1} \frac 1 {\frac 1 2 +i}\right)\frac{(\frac 1 2)(\frac 1 2+1)\ldots (\frac 1 2+n-1)}{n!} \\ &=\left(\sum_{i=0}^{n-1} \frac 2 {2i +1}\right) \frac{(2n-1)!!}{2^n n!} \end{aligned}$$

Problem

1

Which of these sequences is represented by the OGF $\frac 3 {1-z}$?

• 0, 0, 1/2, 0, 1/4, 0, 1/6, …

• 1, 3, 9, 27, 81, 243, …

• 3, 3, 3, 3, 3, …

• 1, 1 + 1/2, 1 + 1/2 + 1/3, …

• 0, 0, 1, 3, 6, 10, …

解：

$$\frac 3 {1-z} =3\sum_{n=0}^{\infty} z^n$$

所以

$$a_n =3$$

2

Suppose that $a_{n}=9 a_{n-1}-20 a_{n-2}$ for $n>1$ with $a_{0}=0$ and $a_{1}=1 .$ What is the value of
$\lim _{n \rightarrow \infty} a_{n} / a_{n-1} ?$

首先对原式进行改写：

$$a_{n}=9 a_{n-1}-20 a_{n-2} +\delta_{n1}$$

那么

$$\begin{aligned} a_nz^n &= 9 a_{n-1}z^n -20a_{n-2}z^n +\delta_{n1}z^n \\ A(z)&= 9zA(z)-20z^2A(z) + z\\ A(z) &=\frac{z}{20z^2-9z+1}\\ &=\frac z{(4z-1)(5z-1)}\\ &=\frac{1}{1-5z} - \frac{1}{1-4z}\\ &= \sum_{n=0}^{\infty} (5^n -4^n)z^n\\ a_n&=5^n -4^n \end{aligned}$$

因此

$$\lim _{n \rightarrow \infty} a_{n} / a_{n-1} = 5$$

3

What is the value of $\sum_{0 \leq k \leq n}\left(\begin{array}{c}{2 k} \\ {k}\end{array}\right)\left(\begin{array}{c}{2 n-2 k} \\ {n-k}\end{array}\right) ?$

解：记

$$a_n=\sum_{0 \leq k \leq n}\left(\begin{array}{c}{2 k} \\ {k}\end{array}\right)\left(\begin{array}{c}{2 n-2 k} \\ {n-k}\end{array}\right)$$

那么

$$\begin{aligned} \sum_{n=0}^{\infty} a_n z^n &=\sum_{n=0}^{\infty} \sum_{0 \leq k \leq n}\left(\begin{array}{c}{2 k} \\ {k}\end{array}\right)\left(\begin{array}{c}{2 n-2 k} \\ {n-k}\end{array}\right) z^n\\ &=\left(\sum_{k=0}^{\infty} \binom {2k}k z^k \right) \left(\sum_{n\ge k}\binom {2n-2k}{n-k} z^{n-k} \right)\\ &=\left(\sum_{k=0}^{\infty} \binom {2k}k z^k \right)^2 \end{aligned}$$

因为

$$\begin{aligned} \frac 1 {\sqrt{1-4z}} &=\sum_{n=0}^{\infty} \binom {-\frac 1 2} {n} (-4z)^n\\ &=\sum_{n=0}^{\infty} \frac{(-\frac 1 2) (-\frac 1 2 -1)\ldots(-\frac 1 2 -n +1)}{n!}(-4)^n z^n\\ &=\sum_{n=0}^{\infty} \frac{(2n-1)!!}{2^n n!} 4^n z^n\\ &=\sum_{n=0}^{\infty} \frac{(2n-1)!! 2^n n !}{ n!n!} z^n \\ &=\sum_{n=0}^{\infty} \binom {2n}n z^n \end{aligned}$$

所以

$$\begin{aligned} \sum_{n=0}^{\infty} a_n z^n &=\frac 1 {1-4z}\\ &=\sum_{n=0}^{\infty} 4^n z^n \end{aligned}$$

即

$$a_n = 4^n$$